package main

import "fmt"

type pair struct {
	x, y int
}

var around = []pair{{-1, 0}, {0, 1}, {0, -1}, {1, 0}}

//92ms 43%,1.9MB 44%
func exist(board [][]byte, word string) bool {
	m, n := len(board), len(board[0])
	vis := make([][]bool, m)
	for i := 0; i < m; i++ {
		vis[i] = make([]bool, n)
	}
	var check func(i, j, k int) bool
	check = func(i, j, k int) bool {
		if board[i][j] != word[k] {
			return false
		}
		if k == len(word)-1 {
			return true
		}
		vis[i][j] = true
		defer func() { vis[i][j] = false }()
		for _, v := range around {
			if ii, jj := i+v.x, j+v.y; ii >= 0 && ii < m && jj >= 0 && jj < n && !vis[ii][jj] {
				if check(ii, jj, k+1) {
					return true
				}

			}
		}
		return false
	}
	for i, v := range board {
		for j := range v {
			if check(i, j, 0) {
				return true
			}
		}
	}
	return false
}

func main() {
	s := "hello"
	for _, v := range s {
		fmt.Println(v)
	}
	fmt.Println(exist([][]byte{{'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}}, "ABCCED"))
}
